package server.simple100;


import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 144. 二叉树的前序遍历
 * <p>
 * 中序遍历 -- 左 中 右
 * 前序遍历 -- 中 左 右
 * 后序遍历 -- 左 右 中
 */
public class LeetCode144 {


	@Test
	public void test() {
		TreeNode treeNode1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
		//TreeNode treeNode1 = new TreeNode(1);
		System.out.println(preorderTraversal(treeNode1));
	}


	public List<Integer> preorderTraversal(TreeNode root) {
		// 1、定义返回对象
		List<Integer> vals = new ArrayList<Integer>();
		// 2、递归遍历 (中 左 右)
		nextNode(root, vals);
		return vals;
	}


	void nextNode(TreeNode root, List<Integer> vals) {
		if (root == null) {
			return;
		}
		// 中 左 右
		// 1、先获取中间节点为当前节点值
		vals.add(root.val);
		// 2、遍历左节点
		nextNode(root.left, vals);
		// 3、遍历右节点
		nextNode(root.right, vals);
	}


	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}
